package main

import (
	"fmt"
	"sort"
)

// 如何找到由其他单词组成的最长单词

func main() {
	strArr := []string{"test", "tester", "testertest", "testing", "apple", "seattle",
		"banana", "batting", "ngcat", "batti", "bat", "testingtester", "testbattingcat"}
	lw := new(longestWord)
	longestStr := lw.getLongestStr(strArr)
	fmt.Println(longestStr)
}

type longestWord struct{}

// 判断字符串 str 是否在字符串数组中
func (p *longestWord) find(strArr []string, str string) bool {
	for _, v := range strArr {
		if str == v {
			return true
		}
	}
	return false
}

// 判断字符串 word 是否能由数组 strArr 中的其他单词组成
// word 为待判断的后缀子串，length 为待判断字符串的长度
func (p *longestWord) isContain(strArr []string, word string, length int) bool {
	ll := len(word)
	if ll == 0 {
		return true
	}

	// 循环取字符串的所有前缀
	for i := 1; i <= ll; i++ {
		// 取到的子串为自己
		if i == length {
			return false
		}

		// 截取一部分字符串
		str := word[0:i]

		// 查询在 strArr 中是否有 str
		if p.find(strArr, str) {
			if p.isContain(strArr, word[i:], length) {
				return true
			}
		}
	}

	return false
}

// 找出由数组中其他字符串组成的最长字符串
func (p *longestWord) getLongestStr(strArr []string) string {
	// 对字符串由大到小排序
	sort.Slice(strArr, func(i, j int) bool {
		return len(strArr[i]) > len(strArr[j])
	})

	// 贪心地从最长的字符串开始判断
	for _, v := range strArr {
		if p.isContain(strArr, v, len(v)) {
			return v
		}
	}

	return ""
}
